package zw_801_900.zw_821_字符的最短距离;

class Solution {
    public static void main(String[] args) {
        String s = "loveleetcode";
        char c = 'e';
        int[] shortest = shortestToChar(s, c);
        for (int i : shortest) {
            System.out.print(i + " ");
        }
    }


    /**
     * 两次遍历
     * idx初始值。 初始值的idx具体设为多少不是很重要, 也可设成INT_MIN/2和INT_MAX/2，
     * 关键在于为了标注在左向右或右向左遍历时等于字母c的首位置还未出现，那此刻的位置就先暂存一个较大的值，在之后的min比较时，会找到正确的小的那个值；
     * 因为在左向右遍历到i时，如果c未出现，那在右向左遍历时，c一定出现在那个i之前，所以两次遍历一定会有找到，取小的那个就是要找的。
     *
     * @param s
     * @param c
     * @return
     */
    public static int[] shortestToChar(String s, char c) {
        int n = s.length();
        int[] ans = new int[n];
        for (int i = 0, idx = -2 * n; i < n; ++i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = i - idx;
        }

        for (int i = n - 1, idx = 2 * n; i >= 0; --i) {
            if (s.charAt(i) == c) {
                idx = i;
            }
            ans[i] = Math.min(ans[i], idx - i);
        }
        return ans;
    }
}
